package com.leetcodehot.problems;

import java.util.ArrayList;
import java.util.List;

public class problems93 {
    private String s;
    private int n;
    List<String> res = new ArrayList<>();
    List<String> list = new ArrayList<>();

    public List<String> restoreIpAddresses(String _s) {
        s = _s;
        n = s.length();
        dfs(0);
        return res;
    }

    private void dfs(int u) {
        int m = list.size();
        if (u == n && m < 4 || u > n)
            return;
        if (m == 4 && u < n)
            return;

        if (m == 4 && u == n) {
            //记录
            //list to res
            StringBuilder str = new StringBuilder();
            for (String s : list) {
                str.append(s);
                str.append(".");
            }
            str.deleteCharAt(str.length() - 1);
            res.add(str.toString());
            return;
        }

        int max = s.charAt(u) == '0' ? u + 1 : n;
        //max为可枚举的范围
        int cur = 0;
        for (int i = u; i < max && i - u < 3; i++) {
            if (cur * 10 + (s.charAt(i) - '0') < 256) {
                cur = cur * 10 + (s.charAt(i) - '0');
                list.add(cur + "");
                dfs(i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}
